package com.cty._05_Ability._62_LastNumberInCircle;

import javafx.scene.shape.Circle;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 * @Auther: cty
 * @Date: 2020/7/25 10:08
 * @Description: 面试题62：圆圈中最后剩下的数字
 * 题目：0, 1, …, n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里
 * 删除第m个数字。求出这个圆圈里剩下的最后一个数字。
 * @version: 1.0
 */
public class LastNumberInCircle {

    private static final int SURPLUS = 1;

    // 方法一：链表模拟圆圈实现
    public static int lastNumberInCircle(int n, int m) {
        if(n<1 || m<1)
            return -1;

        List<Integer> circle = new LinkedList<>();
        for(int i=0; i<n; i++)
            circle.add(i);

        int count = 0;
        while(circle.size() > SURPLUS){
            Iterator<Integer> iterator = circle.iterator();
            while(iterator.hasNext()){
                iterator.next();
                if(++count == m) {
                    iterator.remove();
                    count = 0;
                }
            }  // end while 2
        }  // end while 1

        return circle.get(0);
    }  // end lastNumberInCircle()

    // 方法二：根据规律推导数学公式计算
    public static int lastNumberInCircle2(int n, int m){
        if(n<1 || m<1)
            return -1;

        int last = 0;
        for(int i=2; i<=n; i++)
            last = (last + m) % i;
        return last;
    }  // end lastNumberInCircle()

}  // end class
